﻿#define _CRT_SECURE_NO_WARNINGS 1

//https://leetcode.cn/problems/longest-palindromic-subsequence/
//最⻓回⽂⼦序列


class Solution {
public:
    int longestPalindromeSubseq(string s)
    {
        int n = s.size();
        //创建dp
        vector<vector<int>> dp(n, vector<int>(n));
        for (int i = n - 1; i >= 0; i--)
        {
            for (int j = i; j < n; j++)
            {
                if (s[i] == s[j])
                {
                    if (i == j) dp[i][j] = 1;
                    else if (i + 1 == j) dp[i][j] = 2;
                    else dp[i][j] = dp[i + 1][j - 1] + 2;
                }
                else
                {
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[0][n - 1];
    }
};


//https://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome/
//让字符串成为回⽂串的最⼩插⼊次数（hard）

class Solution {
public:
    int minInsertions(string s)
    {
        int n = s.size();
        //创建dp
        vector<vector<int>> dp(n, vector<int>(n));

        for (int i = n - 1; i >= 0; i--)
        {
            for (int j = i + 1; j < n; j++)
            {
                if (s[i] == s[j])
                    dp[i][j] = dp[i + 1][j - 1];
                else
                    dp[i][j] = min(dp[i][j - 1], dp[i + 1][j]) + 1;

            }
        }
        return dp[0][n - 1];
    }
};